package Offer;

import java.lang.reflect.Array;
import java.util.Arrays;

//13.机器人的运动范围
public class Offer13 {
    public int movingCount(int m, int n, int k) {
        int res =1;
        int used[][] =new int[m][n];
        used[0][0]=1;
        for(int i = 0; i < m;i++ ){
            for(int j =0;j<n;j++){
                int sum = 0;
                int ti = i,tj=j;
                while(ti>0){
                    sum+=(ti%10);
                    ti/=10;
                }
                while(tj>0){
                    sum+=(tj%10);
                    tj/=10;
                }
                boolean left=false,up=false;
                if(j-1>=0 && used[i][j-1]==1)
                    left = true;
                if(i-1>=0 && used[i-1][j]==1)
                    up = true;
                boolean f =left||up;
                if(sum>k || !f)
                    continue;
                else{
                    used[i][j]=1;
                    res++;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Offer13 offer = new Offer13();
        System.out.println(offer.movingCount(1,2,1));
        
    }
}
